package 中等.栈;

import java.util.ArrayList;
import java.util.List;

/**
 * 给你一个数组 target 和一个整数 n。每次迭代，需要从  list =
 * { 1 , 2 , 3 ..., n } 中依次读取一个数字。
 * 请使用下述操作来构建目标数组 target ：
 * "Push"：从 list 中读取一个新元素， 并将其推入数组中。
 * "Pop"：删除数组中的最后一个元素。
 * 如果目标数组构建完成，就停止读取更多元素。
 * 题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
 * 请返回构建目标数组所用的操作序列。如果存在多个可行方案，返回任一即可。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/build-an-array-with-stack-operations
 */
public class 用栈操作构建数组_1441 {

    public static void main(String[] args) {

        System.out.println(buildArray(new int[]{1, 3}, 3));

    }

    /**
     * 模拟
     * target 数组是栈最后的结果
     * n 从 1 开始，如果和栈顶元素不相等，那么 n++ ，从栈中移除掉这些元素
     * 需要 Push Push ... Pop Pop ...
     * 相等时，只需要 Push，推入栈中
     *
     * @param target
     * @param n
     * @return
     */
    public static List<String> buildArray(int[] target, int n) {
        List<String> list = new ArrayList<>();
        int targetIdx = 0;
        int curN = 1;
        while (targetIdx < target.length) {
            int count = 0;
            while (target[targetIdx] != curN) {
                curN++;
                count++;
            }
            for (int i = 0; i < count; i++) {
                list.add("Push");
            }
            for (int i = 0; i < count; i++) {
                list.add("Pop");
            }

            curN++;
            list.add("Push");
            targetIdx++;
        }
        return list;
    }

}
